package pers.qianyu.month_202012.date_20201211;

import org.junit.*;

import java.util.*;
import java.util.stream.*;

/**
 * 22. 括号生成
 * https://leetcode-cn.com/problems/generate-parentheses/
 *
 * @author mizzle rain
 * @date 2020-12-11 14:54
 */
public class GenerateParenthesis {
    private List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        List<String> track = new ArrayList<>();
        recur(track, n, n, n);
        return res;
    }

    private void recur(List<String> track, int left, int right, int n) {
        if (left < 0 || right < 0 || left > right) {
            return;
        }
        if (track.size() == 2 * n) {
            res.add(getStr(track, n));
            return;
        }
        track.add("(");
        recur(track, left - 1, right, n);
        track.remove(track.size() - 1);
        track.add(")");
        recur(track, left, right - 1, n);
        track.remove(track.size() - 1);
    }

    private String getStr(List<String> track, int n) {
        return track.stream().collect(Collectors.joining(""));
    }

    @Test
    public void test1() {
        GenerateParenthesis obj = new GenerateParenthesis();
        List<String> result = obj.generateParenthesis(3);
        result.forEach(System.out::println);
    }
}
